// 成绩排序与名次计算（递归函数示例）
object RecursiveFunctionDemo extends App {
  // 1. 基础递归：计算阶乘（验证递归逻辑）
  def factorial(n: Int): Int = {
    // 基准条件：n<=1时返回1（终止递归）
    if (n <= 1) 1
    // 递归步骤：问题规模减小（n-1）
    else n * factorial(n - 1)
  }

  // 2. 递归排序：快速排序（对成绩列表升序排序）
  def sortScores(scores: List[Int]): List[Int] = {
    // 基准条件：空列表或单元素列表无需排序
    if (scores.length <= 1) scores
    else {
      val pivot = scores.head // 选择第一个元素作为基准
      // 分割列表：小于等于基准的元素 + 大于基准的元素
      val (lessOrEqual, greater) = scores.tail.partition(_ <= pivot)
      // 递归排序子列表，合并结果（升序）
      sortScores(lessOrEqual) :+ pivot :++ sortScores(greater)
    }
  }

  // 3. 递归计算名次：根据成绩列表和排序后的列表，计算每个成绩的名次
  def calculateRanks(scores: List[Int], sortedScores: List[Int] = Nil): List[Int] = {
    if (scores.isEmpty) Nil // 基准条件：空列表返回空名次
    else {
      val currentScore = scores.head
      // 若未传入排序后的列表，先对原始成绩降序排序（名次从高到低）
      val sorted = if (sortedScores.isEmpty) sortScores(scores).reverse else sortedScores
      val rank = sorted.indexOf(currentScore) + 1 // index从0开始，名次+1
      // 递归计算剩余成绩的名次，拼接结果
      rank :: calculateRanks(scores.tail, sorted)
    }
  }

  // 4. 递归查找最高分学生
  case class Student(name: String, score: Int)
  def findTopStudents(students: List[Student]): List[Student] = {
    if (students.isEmpty) Nil // 基准条件：空列表返回空
    else {
      val topScore = students.map(_.score).max // 找到最高分
      // 过滤出所有分数等于最高分的学生
      students.filter(_.score == topScore)
    }
  }

  // 测试递归函数
  println("=== 阶乘计算 ===")
  println(s"5的阶乘是: ${factorial(5)}") // 输出：5的阶乘是: 120

  println("\n=== 成绩排序与名次 ===")
  val mathScores = List(85, 92, 76, 88, 98, 76, 85, 92)
  println(s"原始成绩: $mathScores") // 输出：原始成绩: List(85, 92, 76, 88, 98, 76, 85, 92)
  val sortedScores = sortScores(mathScores)
  println(s"排序后(升序): $sortedScores") // 输出：排序后(升序): List(76, 76, 85, 85, 88, 92, 92, 98)
  val ranks = calculateRanks(mathScores)
  println(s"对应名次: $ranks") // 输出：对应名次: List(3, 6, 1, 5, 8, 1, 3, 6)

  println("\n=== 查找最高分学生 ===")
  val studentList = List(
    Student("张三", 85),
    Student("李四", 92),
    Student("王五", 76),
    Student("赵六", 98)
  )
  val topStudents = findTopStudents(studentList)
  println(s"最高分学生: ${topStudents.map(_.name).mkString(",")}, 分数: ${topStudents.head.score}")
  // 输出：最高分学生: 赵六, 分数: 98
}